/*
 * @lc app=leetcode.cn id=39 lang=golang
 * @lcpr version=30118
 *
 * [39] 组合总和
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
func combinationSum(candidates []int, target int) [][]int {
	res := make([][]int, 0)

	dfs(candidates, target, 0, 0, []int{}, &res)

	return res
}

func dfs(candidates []int, target, start int, sum int, path []int, res *[][]int) {
	if sum == target {
		*res = append(*res, append([]int{}, path...))
		return
	}
	if sum > target || start >= len(candidates) {
		return
	}

	for i := start; i < len(candidates); i++ {
		path = append(path, candidates[i])
		dfs(candidates, target, i, sum+candidates[i], path, res)
		path = path[:len(path)-1]
	}
}

// @lc code=end

/*
// @lcpr case=start
// [2,3,6,7]\n7\n
// @lcpr case=end

// @lcpr case=start
// [2,3,5]\n8\n
// @lcpr case=end

// @lcpr case=start
// [2]\n1\n
// @lcpr case=end

*/

